package com.peng.leetcode.list;

import java.util.Arrays;
import java.util.Random;

/**
 * SkipList
 * 1206. 设计跳表
 * https://leetcode.cn/problems/design-skiplist/
 *
 * @author: lupeng6
 * @create: 2023/3/19 18:49
 */
public class Skiplist {

    public static void main(String[] args) {
        // ["Skiplist","add","add","add","search","add","search","erase","erase","search"]
        // [[],        [1],   [2],  [3],  [0],     [4], [1],     [0],     [1],    [1]]
        Skiplist s = new Skiplist();
        s.add(1);
        s.add(2);
        s.add(3);
        System.out.println(s.search(0));
        s.add(4);
        System.out.println(s.search(1));
        System.out.println(s.erase(0));
        System.out.println(s.erase(1));
        System.out.println(s.search(1));
    }

    private Node head;
    private Random random;
    private static final double FACTOR = 0.25;
    private static final int MAX_LEVEL = 32;
    private int currMaxLevel;

    public Skiplist() {
        this.head = new Node(MAX_LEVEL);
        this.random = new Random();
        this.currMaxLevel = 1;
    }

    public boolean search(int target) {
        Node curr = this.head;
        for (int i = currMaxLevel - 1; i >= 0; i--) {
            while (curr.forward[i] != null && curr.forward[i].val < target) {
                curr = curr.forward[i];
            }
        }
        curr = curr.forward[0];
        return curr != null && curr.val == target;
    }

    /**
     * 添加元素
     * 1. 在每一层中找到 < num 的forward
     * 2. 新创建一个forward层级temp，将找到的forward用temp记录下来
     * 3. 创建新的Node，newNode.forward[i] = temp[i].forward[i],新节点的forward指向
     * 3. temp[i].forward[i] = newNode
     */
    public void add(int num) {
        Node[] temp = new Node[MAX_LEVEL];
        Arrays.fill(temp, this.head);
        Node curr = this.head;
        for (int i = currMaxLevel - 1; i >= 0; i--) {
            while (curr.forward[i] != null && curr.forward[i].val < num) {
                curr = curr.forward[i];
            }
            temp[i] = curr;
        }
        int level = randomLevel();
        this.currMaxLevel = Math.max(level, currMaxLevel);
        Node newNode = new Node(num, level);
        for (int i = 0; i < level; i++) {
            newNode.forward[i] = temp[i].forward[i];
            temp[i].forward[i] = newNode;
        }
    }

    public boolean erase(int num) {
        Node[] temp = new Node[MAX_LEVEL];
        Node curr = this.head;
        for (int i = MAX_LEVEL - 1; i >= 0; i--) {
            while (curr.forward[i] != null && curr.forward[i].val < num) {
                curr = curr.forward[i];
            }
            temp[i] = curr;
        }
        curr = curr.forward[0];
        if (curr == null || curr.val != num) {
            return false;
        }
        for (int i = 0; i < currMaxLevel; i++) {
            if (temp[i].forward[i] != curr) {
                break;
            }
            temp[i].forward[i] = curr.forward[i];
        }
        while (currMaxLevel > 1 && head.forward[currMaxLevel - 1] == null) {
            currMaxLevel--;
        }
        return true;
    }

    private int randomLevel() {
        int level = 1;
        while (level < MAX_LEVEL && random.nextDouble() < FACTOR) {
            level++;
        }
        return level;
    }

    private static class Node {
        Integer val;
        Node[] forward;

        public Node(int val, int level) {
            this.val = val;
            this.forward = new Node[level];
        }

        public Node(int level) {
            this.forward = new Node[level];
        }
    }
}
